package com.njupt.Array;

import java.util.Arrays;

public class SortedSquares {

    /**
     * 法一 暴力解法
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i <nums.length ; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);

        return nums;
    }

    /**
     * 法二 双指针法
     * 分析：有序数组平方之后的最大值只会出现在首尾两端，整个数组是先单调递减，后单调递增
     * i，j指向nums数组的首和尾
     * 用空间换时间的思想，新开辟一个数组，将结果保存在数组中
     * @param nums
     * @return
     */
    public int[] sortedSquares1(int[] nums) {
        int index = nums.length-1;
        int left = 0; int right = nums.length-1;
        int[] result = new int[nums.length];

        while(left<=right){
            if(nums[left] * nums[left] < nums[right] * nums[right]){
                result[index--] = nums[right] * nums[right];
                right--;
            }else {
                result[index--] = nums[left] * nums[left];
                left++;
            }
        }
        return result;
    }

    /**
     * 这个数组平方之后负数部分是单调递减，非负数部分是单调递增，那么可以采用类似的归并排序
     * @param nums
     * @return
     */
    public int[] sortedSquares2(int[] nums){
        int negative = -1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<0){
                negative = i;
            }else {
                break;
            }
        }

        int left = negative; int right = negative +1;
        int[] result = new int[nums.length];
        int index = 0;
        while(left>=0 && right< nums.length){
            if(nums[left] * nums[left] < nums[right] * nums[right]){
                result[index++] = nums[left] * nums[left];
                left--;
            }else {
                result[index++] = nums[right] * nums[right];
                right++;
            }
        }

        while(left>=0) {
            result[index++] = nums[left] * nums[left];
            left--;
        }
        while(right< nums.length) {
            result[index++] = nums[right] * nums[right];
            right++;
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        SortedSquares test = new SortedSquares();
        int[] result = test.sortedSquares2(nums);
        System.out.println(Arrays.toString(result));
    }
}
